COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	VI.  Matching 
C00016 00003	A.  definition of matching 
C00017 00004	A.  definition of matching 
C00018 ENDMK
C⊗;
VI.  Matching 

A.  we only care about computation numbers from the point of view that 
	they stipulate a partial ordering 
B.  why not lexicographic minimum (Feb. 22,1974) 
C.  loop unrolling and loop economy discussions 
D.  modifications to REDERIVE - PASS4 
	1.   Powerset of labels branched to 
		in backward direction will yield one rederived program for 
		each element of powerset 
	2.  Question:  When determining argument values should we use 
		matching as in the matching phase or stick to redundant 
		computations.  Think about it and try to justify choice.  
	    Answer:  Redundant computations is the right solution since 
		if a computation is repeated in the beginning of a function 
		as well as prior to the call, then its elimination  (or 
		bypassing) may be wrong.  For example, suppose a function 
		known to read and modify a special variable fits this 
		criterion.  Moreover, the arguments are identical.  In this 
		case, its bypassing would be a mistake.  The function could 
		be of a nature that increments the SPECIAL variable.  This 
		should only be mentioned in Chapter 6 once the distinction 
		between matching and redundancy is explained.  
E.  Distinction between matching and duplicate predicates 
F.  Unspecified parameters 
G.  Pinpointing errors 
	1.  computations out of order 
	2.  missing computations - a value was computed in the rederived form 
		which was not specified in the canonical form or out of order.  
		This could result from
	3.  indicate when a location was garbaged - storage history field in 
		data descriptor 
	4.  missing condition 
	5.  mismatching conclusion - the conclusion in the rederived form does 
		not match the conclusion as specified by the canonical form.  
	6.  missing FN list computation in rederived form (i.e. a computation 
		not used as a subexpression of a predicate or a result was not 
		computed by the assembly language program).  
	7.  unknown conclusion in the rederived form resulting from an error in 
		the assembly language program.  
	8.  anything else? 
	9.  illustrate by examples 
H.  Show how depth first numbering is used to enable us to tell what is computed 
	in all subtrees.  
I.  Extraneous computations 
J.  Matching algorithm and various passes 
	1.  all duplicate computations have been removed from canonical form and 
		rederived form 
	2.  redundant first instances of computation have been removed from 
		canonical form and rederived form 
	3.  we no longer concern ourselves with redundant first instances of 
		computation by comments in Chapter 4 regarding this procedure 
	4.  implicit vs explicit match (Oct 14,1974) 
	5.  constantly renumbering 
	6.  use induction for backward jumps 
	7.  special handling for assignment (SETQ, SET)? 
	8.  indicate the use of axiom (8) and axiom (1) - we search for inevitable 
		computations; not just predicates as done in JMC 
	9.  termination 
	10.  Sometimes manipulate canonical form and sometimes rederived form.  
		a.  We take the basic approach that the rederived program represents 
			a program and we wish to manipulate the canonical form in 
			legal ways to obtain a match.  When this is done, we say 
			that the programs are equivalent.  This will account for 
			rearranging of conditions as well as the order of performing 
			computations (i.e. order of argument evaluation).  Thus by 
			finding equivalence preserving transformations we are 
			proving that the rederived form is equivalent to the 
			canonical form.  
		b.  We manipulate the rederived form to match the canonical form 
			when we try to match backward jumps.  The canonical form 
			consists of the already manipulated version.  This is 
			because we will be trying out various versions of 
			abbreviated rederived forms with induction.  
		c.  The above is necessary especially when conditions have been 
			rearranged.  Problem here is that if we use the original 
			canonical form, then conditions have not been rearranged.  
			However, when we expand recursive call mismatches we use 
			the rederived forms plugged into the mismatching function 
			calls in the canonical form since by induction, the 
			canonical form has already been reordered to correspond 
			to the order implied by the rederived form.  
	11.  Whenever a predicate is introduced into canonical form via axiom (1) 
		we must apply duplicate computation removal to both the conclusion 
		and alternative clauses as well as renumber since axiom (1) is 
		(p→a,a).  Renumbering is to insure depth first property that all 
		computations in left subtree have a higher number than those in 
		right subtree.  
K.  EQ vs EQUAL when can use either one is irrelevant due to manner in which 
	we match.  
L.  Predicates with identical conclusion and alternative clauses (p→a,a) and 
	use FN as an example.  Sort of like factoring.  
M.  When matching we must consider the case of a computation of CAR(<expr>) which 
	can not be matched even though CDR(<expr>) was matched or vice versa.  In 
	this case we currently say that inequivalence is the case since a 
	computation is performed in one form and not in the other.  Actually, 
	we should say that if CAR (CDR) is legal then so is CDR (CAR).  This is 
	because no side effect can occur - i.e. recall that the problem was that CAR 
	and CDR are not defined when their argument is non-atomic.  But the act of 
	computing one of one them safely, implies that the other can also be 
	computed safely.  This problem is quite common in a LISP implementation 
	where a word represents more than one LISP entity - i.e. a pointer to CAR 
	in the left halfword and a pointer to CDR in the right halfword.  In such a 
	case we may access an entire word when in fact we only desire a specific 
	half.  	A similar 
	consideration is if ATOM(A) is known not to be true, then CAR(A) and CDR(A) 
	are also safe provided that they are performed after the ATOM test.  
    One solution is to place CDR(A) on the FN list (and on UNREFERENCED) whenever 
	CAR(A) is seen and similarly for CAR(A) and CDR(A).  Also place CAR(A) and 
	CDR(A) on the FN list  (and on UNREFERENCED) whenever ATOM(A) is known to be 
	NIL (i.e. false).  The only problem is that when we remove redundant first 
	instances of computation (see canonical form and also prostprocessing stage 
	of rederived form) involving modification of heads or tails, and if an 
	access to the head or tail appears as an argument in a non-result slot to an 
	FN construct, then it is not considered as an access operation.  
    We propose a solution for a CAR(A) operation that cannot be matched.  This 
	procedure is applied prior to removing redundant first instances of a 
	computation involving modification of heads or tails of elements of the List 
	Structure at the end of the canonical form process described in 
	Chapter 3 and during the postprocessing stage of the rederivation process.  
	It should be noted that the same solution would hold for CDR(A) 
	(actually need to replace CAR by CDR and CDR by CAR in the discussion).  
	Examine the non-result 
	arguments of FN constructs for instances of CAR(A).  If all such occurrences 
	appear as non-result arguments of FN constructs, and if CDR(A) appears in 
	a predicate or in the result of a path containing CAR(A), then CAR(A) can 
	safely be removed from the FN list.  By safely removed we mean that its 
	computation qualifies as a primitive operation.  We leave the case of ATOM 
	for future work although it is clear that it would be handled in much the 
	same manner.  
N.  Proof procedure is machine independent and likewise for intermediate 
	representation.  
Q.  Matching 
	1.  no backward jumps 
		a.  match rederived against canonical manipulating canonical 
		b.  numbering 
		c.  computations 
			i.  explicit 
		       ii.  implicit 
		d.  conditions 
			i.  EQ, ATOM 
		       ii.  EQUAL and check redundant since EQUAL is not primitive 
		e.  termninal node 
R.  Give NEXT as an example of proof 

A.  definition of matching 
B.  matching algorithm 
C.  loop unrolling versus loop economy 
D.  changes to rederivation process 
E.  modification for backward jumps 
F.  type of errors that can be detected 
A.  definition of matching 
B.  matching algorithm 
C.  loop unrolling versus loop economy 
D.  changes to rederivation process 
E.  modification for backward jumps 
F.  type of errors that can be detected